"""
队列有两种实现形式，分为两种：数组和链表。
"""
"""
链表实现队列
"""
"""
复杂度分析
队列属于常见的一种线性结构，对于出队和进队而言，时间复杂度都为 O(1)
"""


# 定义结点
class Node(object):
    def __init__(self, elem, next=None):
        self.elem = elem
        self.next = next


# 定义队列
class Queue(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    # 入队
    def enqueue(self, elem):
        node = Node(elem)
        # 队列为空, 新结点既是头又是尾
        if self.is_empty():
            self.head = node
            self.tail = node
        # 队列非空
        else:
            # 原来的队尾的next指向新结点
            self.tail.next = node
            # 把新结点设置为新的队尾
            self.tail = node

    # 出队
    def dequeue(self):
        if self.is_empty():
            print("空队列, 无法出队")
        else:
            # 把队头元素的值取出来
            result = self.head.elem
            # 把第二个元素设置成队头
            self.head = self.head.next
            # 返回出队元素的值
            return result

    # 查看队头元素的值
    def get_head(self):
        if self.is_empty():
            print("空队列, 没有队头元素")
        else:
            return self.head.elem

    # 查看队尾元素的值
    def get_tail(self):
        if self.is_empty():
            print("空队列, 没有队尾元素")
        else:
            return self.tail.elem

    # 打印队列
    def print_queue(self):
        print("queue:")
        temp = self.head
        queue = []
        while temp is not None:
            queue.append(temp.elem)
            temp = temp.next
        print(queue)

